home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / NTUMIN10.ARJ / LOGMIN_C.C < prev    next >
C/C++ Source or Header  |  1992-03-12  |  12KB  |  340 lines
  1. /****************************************************************************
  2.  *
  3.  *      Program name : LOGMIN_C.C
  4.  *
  5.  *    Written By : Eng-Huat Ong and Kian-Mong Low.
  6.  *
  7.  *      This is the actual minimization algorithm. Variation from the actual
  8.  *    LOGMIN algorithm is as follows:
  9.  *        1.    Minterms with adjacency 0 or 1 is minimised first
  10.  *        2.    Select next minterm in increasing order of adjacency
  11.  *        3.    To shrink the CPT, select an adjacent term, mi that has the
  12.  *            largest wi AND is already covered
  13.  *
  14.  * --------------------------------------------------------------------------
  15.  *    Copyright (c) 1992. All Rights Reserved. Nanyang Technological
  16.  *    University.
  17.  *
  18.  *    You are free to use, copy and distribute this software and its
  19.  *    documentation providing that:
  20.  *
  21.  *        NO FEE IS CHARGED FOR USE, COPYING OR DISTRIBUTION.
  22.  *
  23.  *        IT IS NOT MODIFIED IN ANY WAY.
  24.  *
  25.  *        THE COPYRIGHT NOTICE APPEAR IN ALL COPIES.
  26.  *
  27.  *    This program is provided "AS IS" without any warranty, expressed or
  28.  *    implied, including but not limited to fitness for any particular
  29.  *    purpose.
  30.  *
  31.  *    If you find NTUMIN fast, easy, and useful, a note or comment would be
  32.  *    appreciated. Please send to:
  33.  *
  34.  *        Boon-Tiong Tan or Othman Bin Ahmad
  35.  *        School of EEE
  36.  *        Nanyang Technological University
  37.  *        Nanyang Avenue
  38.  *        Singapore 2263
  39.  *        Republic of Singapore
  40.  *
  41.  ***************************************************************************/
  42.  
  43. #include <stdio.h>
  44. #include <stdlib.h>
  45. #include <string.h>
  46. #define mask8 255
  47.  
  48. unsigned char   *logmin_c(a, b)              /* pointer to a & b array passed */
  49. unsigned char   *a, *b;
  50.  
  51. {
  52.    unsigned short   pterm, ma, mb, *pm, pos;
  53.    unsigned  long   m, k, topow();
  54.    register  long   i, wo, wi;
  55.    register  char   j;
  56.          char   test;
  57.    unsigned  char   *c, *d, *e, *s, *temp, count, limit, adj0, adji;
  58.    unsigned  char   n, adj, adjacency(), nspm, cover;
  59.    unsigned  char   *adjacent(), *reduce(), *cpt(), *ssm(), adj_of_mi();
  60.  
  61.  
  62.    mb = *(b+2)<<8 | *(b+1);            /* no. of minterms in b-array */
  63.  
  64.    n    = *a;                          /* no. of variables */
  65.    nspm = *(a+3);                      /* no. of bytes/minterm */
  66.    ma = *(a+2)<<8 | *(a+1);            /* no. of minterms in a-array */
  67.  
  68.    temp = (unsigned char *) malloc(nspm+1);        /* temporary storage */
  69.    if (temp == 0)
  70.       {
  71.      printf("Out of memory -- LOGMIN_C, *temp\n");
  72.      printf("Program terminated - 1\n");
  73.      exit(0);
  74.       }
  75.  
  76.    s = (unsigned char *) malloc(4);                /* header of s-array */
  77.    if (s == 0)
  78.       {
  79.      printf("Out of memory -- LOGMIN_C, *s\n");
  80.      printf("Program terminated - 2\n");
  81.      exit(0);
  82.       }
  83.  
  84.    pterm = 0;                                /* no. of product term */
  85.  
  86.    /***
  87.     ***  MINIMIZE ALL MINTERMS WITH ADJACENCY OF 0 & 1 FIRST
  88.     ***/
  89.  
  90.    for (i=0; i<mb; i++)                      /* for adj = 0 or 1 */
  91.       {
  92.      *b = n;                             /* assign back to n */
  93.  
  94.      memcpy(temp, (b+4+nspm*i), nspm);   /* pick a minterm from b-array */
  95.      c = adjacent(temp, a, 1);           /* obtain the adjacent terms */
  96.      adj = *(c+1);                       /* adjacency of minterm */
  97.  
  98.      if (adj <= 1)                       /* adjacency 0 or 1 */
  99.         {
  100.            d = cpt(c);                   /* generate CPT */
  101.  
  102.            s = (unsigned char *) realloc(s,4+n*(pterm+1));   /* more space */
  103.            if (s == 0)
  104.           {
  105.              printf("Out of memory -- LOGMIN_C, *s\n");
  106.              printf("Program terminated - 3\n");
  107.              exit(0);
  108.           }
  109.            memcpy ((s+4+n*pterm),d,n);   /* add CPT to soln array */
  110.            pterm++;                      /* product term count */
  111.  
  112.            b = reduce(c,b,i);            /* remove minterms covered from b-array */
  113.            i = (char) *b;                /* index pointer of b-array */
  114.            mb = *(b+2)<<8 | *(b+1);      /* value of mb altered in b-array */
  115.  
  116.            free(d);                    /* free pointer */
  117.         }
  118.      free(c);                            /* free pointer */
  119.       }
  120.  
  121.    /***
  122.     ***  MINIMIZE MINTERMS WITH INCREASING ADJACENCY GREATER THAN 1
  123.     ***/
  124.  
  125.    limit = 2;                               /* next adjacency limit */
  126.  
  127.    while (mb > 0)                           /* not all minterms covered */
  128.       {
  129.      for (i=0; i<mb; i++)               /* remaining minterms in b-array */
  130.         {
  131.            *b = n;                      /* assign back to n */
  132.  
  133.            memcpy(temp, (b+4+nspm*i), nspm);   /* pick a minterm from b-array */
  134.            c = adjacent(temp, a, limit);       /* obtain the adjacent terms */
  135.            adj = *(c+1);                       /* adjacency of minterm */
  136.  
  137.            if (adj == limit)                   /* next adjacency limit */
  138.           {
  139.              /***
  140.               ***  GENERATE SSM AND TEST FOR COVERAGE BY FUNCTION
  141.               ***/
  142.  
  143.              d = cpt(c);                   /* generate CPT */
  144.              e = ssm(d);                   /* generate SSM */
  145.              m = topow(*(e+1));            /* no. of SSM terms */
  146.  
  147.              for (j=0; j<m; j++)            /* check for SSM coverage */
  148.             {
  149.                memcpy (temp, (e+4+nspm*j), nspm);  /* pick SSM term */
  150.                test = exist (temp, a, ma);
  151.                if (test == -1)           /* SSM term not in a-array */
  152.                   break;
  153.             }
  154.  
  155.              /***
  156.               ***  ALL SSM COVERED BY THE FUNCTION, SELECT CPT AS PRODUCT TERM
  157.               ***/
  158.  
  159.              if (test == 0)                 /* all SSM's covered by fn */
  160.             {
  161.                if (m > 65536)                  /* too many SSM terms */
  162.                   {
  163.                  printf("Product Term Too Huge \n");
  164.                  printf("Program terminated \n");
  165.                  exit(0);
  166.                   }
  167.                *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  168.                *(e+2) = (m-1)>>8 & mask8;
  169.                b = reduce(e,b,i);        /* remove minterms covered from b-array */
  170.                i = (char) *b;            /* update pointer to b-array */
  171.                mb = *(b+2)<<8 | *(b+1);  /* no. of minterms in b-array */
  172.  
  173.                s = (unsigned char *) realloc(s, 4+n*(pterm+1)); /* more space */
  174.                if (s == 0)
  175.                   {
  176.                  printf("Out of memory -- LOGMIN_C, *s\n");
  177.                  printf("Program terminated - 4\n");
  178.                  exit(0);
  179.                   }
  180.                memcpy((s+4+n*pterm),d,n);     /* add CPT to soln array */
  181.                pterm++;                       /* no. of product terms */
  182.  
  183.                free(d);                       /* free pointers */
  184.                free(e);
  185.             }
  186.              else
  187.             {
  188.                /***
  189.                 ***  SSM NOT COVERED BY THE FUNCTION
  190.                 ***/
  191.  
  192.                free(d);                       /* free pointer */
  193.                cover =0;                      /* coverage status */
  194.  
  195.                while (!cover)        /* do until shrinked SSM is covered */
  196.                   {
  197.                  /***
  198.                   ***  OBTAIN AN ARRAY, PM OF POSITIONS OF ADJACENT TERMS,
  199.                   ***  MI WITH THE LARGEST WI
  200.                   ***/
  201.  
  202.                  wo = -1;                        /* initial value */
  203.                  for (j=0; j<adj; j++)           /* do for all adjacent terms */
  204.                     {
  205.                        memcpy(temp,(c+4+nspm*(j+1)),nspm); /* pick adjacent term */
  206.  
  207.                        wi = adj_of_mi(temp,e,a);           /* obtain wi */
  208.                        if (wi>wo)
  209.                       {
  210.                          if (wo != -1)                 /* not the first */
  211.                         free(pm);
  212.                          wo = wi;                      /* new lowest value */
  213.                          count = 1;                    /* reset count to 1 */
  214.  
  215.                          pm = (unsigned short *) malloc(2);  /* space for pm */
  216.                          if (pm==0)
  217.                         {
  218.                            printf("Out of memory -- LOGMIN_C, *pm\n");
  219.                            printf("Program terminated - 5\n");
  220.                            exit(0);
  221.                         }
  222.                          *pm = j;                      /* first element */
  223.                       }
  224.                        else if (wi==wo)                    /* wi as large */
  225.                       {
  226.                          count++;                      /* no. of element in pm-array */
  227.  
  228.                          pm = (unsigned short *) realloc (pm, 2*count);  /* more space */
  229.                          if (pm==0)
  230.                         {
  231.                            printf("Out of memory -- LOGMIN_C, *pm\n");
  232.                            printf("Program terminated - 6\n");
  233.                            exit(0);
  234.                         }
  235.                          *(pm+count-1) = j;            /* elements of pm-array */
  236.                       }
  237.                     }
  238.                  free(e);
  239.  
  240.                  /***
  241.                   ***  SELECT FROM PM-ARRAY, AN ADJACENT TERM THAT HAS ALREADY BEEN COVERED
  242.                   ***/
  243.  
  244.                  for (j=0; j<count; j++)              /* do for all element in pm-array */
  245.                     {
  246.                        memcpy(temp, (c+4+nspm*(1+ *(pm+j))), nspm);    /* pick adj term */
  247.                        test = exist(temp,b,mb);
  248.                        if (test == -1)                               /* already covered */
  249.                       break;
  250.                     }
  251.  
  252.                  if (j==count)                     /* select the 1st if all not covered */
  253.                     j = 0;
  254.  
  255.                  adj--;                            /* no. of adj terms in c-array */
  256.                  *(c+1) = adj;                     /* adjacency after shrinking CPT */
  257.                  pos = *(pm+j);                    /* required position of adj term */
  258.  
  259.                  free(pm);                         /* free pointer */
  260.  
  261.                  /***
  262.                   ***  SHRINK CPT (REMOVE 1 ADJACENT TERM FROM C-ARRAY), GENERATE NEW CPT, SSM
  263.                   ***  AND TEST FOR COVERAGE BY FUNCTION
  264.                   ***/
  265.  
  266.                  memcpy((c+4+nspm*(1+pos)), (c+4+nspm*(2+pos)), nspm*(adj-pos));  /* shrink CPT */
  267.  
  268.                  c = (unsigned char*) realloc(c, 4+nspm*(1+adj));   /* reduce space */
  269.                  if (c==0)
  270.                     {
  271.                        printf("Out of memory -- LOGMIN_C, *c\n");
  272.                        printf("Program terminated - 7\n");
  273.                        exit(0);
  274.                     }
  275.  
  276.                  d = cpt(c);                  /* generate CPT */
  277.                  e = ssm(d);                  /* generate SSM */
  278.                  m = topow(*(e+1));           /* no. of SSM terms */
  279.  
  280.                  for (k=0; k<m; k++)          /* check SSM coverage by function */
  281.                     {
  282.                        memcpy(temp, (e+4+nspm*k), nspm);  /* pick SSM term */
  283.                        test = exist(temp,a,ma);
  284.                        if (test == -1)                    /* SSM term not covered */
  285.                       break;
  286.                     }
  287.  
  288.                  /***
  289.                   ***  SHRINKED SSM COVERED BY FUNCTION, REDUCE B-ARRAY
  290.                   ***  AND SELECT SHRINKED CPT AS PRODUCT TERM
  291.                   ***/
  292.  
  293.                  if (test==0)                   /* SSM covered */
  294.                     {
  295.                        if (m > 65536)                  /* too many SSM terms */
  296.                       {
  297.                          printf("Product Term Too Huge \n");
  298.                          printf("Program terminated \n");
  299.                          exit(0);
  300.                       }
  301.                        *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  302.                        *(e+2) = (m-1)>>8 & mask8;
  303.                        b = reduce(e, b, i);     /* remove minterms covered from b-array */
  304.                        i = (char) *b;           /* update pointer to b-array */
  305.                        mb = *(b+2)<<8 | *(b+1); /* no. of minterms in b-array */
  306.  
  307.                        s = (unsigned char *) realloc(s, 4+n*(pterm+1));  /* more space */
  308.                        if (s==0)
  309.                       {
  310.                          printf("Out of memory -- LOGMIN_C, *s\n");
  311.                          printf("Program terminated - 8\n");
  312.                          exit(0);
  313.                       }
  314.                        memcpy ((s+4+n*pterm), d, n);      /* add shrinked CPT to soln array */
  315.                        pterm++;                           /* no. of product terms */
  316.  
  317.                        cover = 1;                         /* coverage status */
  318.                        free(e);                           /* free pointer */
  319.                     }
  320.                  free (d);                      /* free pointer */
  321.                   }
  322.             }
  323.           }
  324.            free(c);                     /* free pointer */
  325.         }
  326.      limit++;
  327.       }
  328.    *s = n;                           /* no. of variables */
  329.    *(s+1) = pterm & mask8;           /* no. of product terms in 2 bytes */
  330.    *(s+2) = pterm>>8 & mask8;
  331.  
  332.    free(temp);                       /* free pointer */
  333.    free(a);
  334.    free(b);
  335.  
  336.    return(s);                        /* return solution array */
  337. }
  338.  
  339.  
  340.